#include <stdlib.h>
#include <string.h>
static void __copy(void * e1, void * e2, long int size) {
	long int i;

	char * b1 = e1;
	char * b2 = e2;

	for (i = 0; i < size; i++) {
		*b1 = *b2;
		b1++;
		b2++;
	}
}
static void __gqsort(void * data, int lo, int ho, long int unit_size, int (*compare)(void * e1, void * e2)) {

	/* Elements */
	void * pivot;
	void * left;
	void * right;
	void * tmp;

	/* Indexes */
	long int l, h, pi;

	tmp = calloc(1, unit_size);

	l = lo;
	h = ho;

	if (ho > lo) {

		pi = (lo + ho) >> 1;
		pivot = data + (pi * unit_size);

		left = data + (l * unit_size);
		while ((l < ho) && (compare(left, pivot) < 0)) {
			l++;
			left = data + (l * unit_size);
		}

		right = data + (h * unit_size);
		while ((h > lo) && (compare(right, pivot) > 0)) {
			h--;
			right = data + (h * unit_size);
		}

		if (l <= h) {
			//strncpy(tmp, left, unit_size);
			//strncpy(left, right, unit_size);
			//strncpy(right, tmp, unit_size);
			__copy(tmp, left, unit_size);
			__copy(left, right, unit_size);
			__copy(right, tmp, unit_size);
			l++;
			h--;
		}
		free(tmp);
		if (lo < h) __gqsort(data, lo, h, unit_size, compare);
		if (l < ho) __gqsort(data, l, ho, unit_size, compare);
	}
}
/* ========================================================================== */
void gqsort(void * base, long int total_elements, long int unit_size, int (*compare)(void * e1, void * e2)) {

	long int lo;
	long int ho;

	lo = 0;
	ho = total_elements - 1;

	__gqsort(base, lo, ho, unit_size, compare);

}
/* ========================================================================== */
static void __qsort_char(char * data, int lo, int ho) {

	/* Elements */
	char pivot;
	char left;
	char right;
	char tmp;

	/* Indexes */
	int l, h, pi;

	l = lo;
	h = ho;

	if (ho > lo) {

		pi = (lo + ho) >> 1;
		pivot = data[pi];

		left = data[l];
		while ((l < ho) && ((left - pivot) < 0)) {
			l++;
			left = data[l];
		}

		right = data[h];
		while ((h > lo) && ((right - pivot) > 0)) {
			h--;
			right = data[h];
		}

		if (l <= h) {
			tmp = left;
			left = right;
			right = tmp;

			l++;
			h--;
		}

		if (lo < h) __qsort_char(data, lo, h);
		if (l < ho) __qsort_char(data, l, ho);
	}
}
static void __qsort_int(int * data, int lo, int ho) {

	/* Elements */
	int pivot;
	int left;
	int right;
	int tmp;

	/* Indexes */
	int l, h, pi;

	l = lo;
	h = ho;

	if (ho > lo) {

		pi = (lo + ho) >> 1;
		pivot = data[pi];

		left = data[l];
		while ((l < ho) && ((left - pivot) < 0)) {
			l++;
			left = data[l];
		}

		right = data[h];
		while ((h > lo) && ((right - pivot) > 0)) {
			h--;
			right = data[h];
		}

		if (l <= h) {
			tmp = left;
			left = right;
			right = tmp;

			l++;
			h--;
		}

		if (lo < h) __qsort_int(data, lo, h);
		if (l < ho) __qsort_int(data, l, ho);
	}
}
static void __qsort_float(float * data, int lo, int ho) {

	/* Elements */
	float pivot;
	float left;
	float right;
	float tmp;

	/* Indexes */
	int l, h, pi;

	l = lo;
	h = ho;

	if (ho > lo) {

		pi = (lo + ho) >> 1;
		pivot = data[pi];

		left = data[l];
		while ((l < ho) && ((left - pivot) < 0)) {
			l++;
			left = data[l];
		}

		right = data[h];
		while ((h > lo) && ((right - pivot) > 0)) {
			h--;
			right = data[h];
		}

		if (l <= h) {
			tmp = left;
			left = right;
			right = tmp;

			l++;
			h--;
		}

		if (lo < h) __qsort_float(data, lo, h);
		if (l < ho) __qsort_float(data, l, ho);
	}
}

void quicksort(float * data, int first, int last) {
	int pivot, j, i;
	float temp;

	if (first < last) {
		pivot = first;
		i = first;
		j = last;

		while (i < j) {
			while (data[i] <= data[pivot] && i < last)
				i++;
			while (data[j] > data[pivot])
				j--;
			if (i < j) {
				temp = data[i];
				data[i] = data[j];
				data[j] = temp;
			}
		}

		temp = data[pivot];
		data[pivot] = data[j];
		data[j] = temp;
		quicksort(data, first, j - 1);
		quicksort(data, j + 1, last);

	}
}
/* ========================================================================== */
void qsort_char(char * base, int total_elements) {

	__qsort_char(base, 0, total_elements - 1);

}
void qsort_int(int * base, int total_elements) {

	__qsort_int(base, 0, total_elements - 1);

}
void qsort_float(float * base, int total_elements) {

	__qsort_float(base, 0, total_elements - 1);

}
